window.onload = function () {
    /**
     * 387. 字符串中的第一个唯一字符
     */
    console.log(firstUniqChar("leetcode"))

    /**
     * 5. 最长回文子串
     */
    console.log(longestPalindrome("babad"))

    /**
     * 44. 通配符匹配
     */
    console.log(isMatch("aa", "a"))
}

/**
 * 387. 字符串中的第一个唯一字符
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function (s) {
    const position = new Map();
    const n = s.length;
    for (let [i, ch] of Array.from(s).entries()) {
        if (position.has(ch)) {
            position.set(ch, -1);
        } else {
            position.set(ch, i);
        }
    }
    let first = n;
    for (let pos of position.values()) {
        if (pos !== -1 && pos < first) {
            first = pos;
        }
    }
    if (first === n) {
        first = -1;
    }
    return first;
};

/**
 * 5. 最长回文子串
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    if (!s || s.length < 2) {
        return s;
    }
    let start = 0, end = 0;
    let n = s.length;
    // 中心扩展法
    let centerExpend = (left, right) => {
        while (left >= 0 && right < n && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
    for (let i = 0; i < n; i++) {
        let len1 = centerExpend(i, i);
        let len2 = centerExpend(i, i + 1);
        // 两种组合取最大回文串的长度
        let maxLen = Math.max(len1, len2);
        if (maxLen > end - start) {
            // 更新最大回文串的首尾字符索引
            start = i - ((maxLen - 1) >> 1);
            end = i + (maxLen >> 1);
        }
    }
    return s.substring(start, end + 1);
};

/**
 * 44. 通配符匹配
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function (s, p) {
    const m = s.length, n = p.length

    // 状态定义：dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配
    const dp = new Array(m + 1).fill(false).map(() => new Array(n + 1).fill(false))

    // 状态初始化
    // 1. 空字符串和空字符串是匹配的
    dp[0][0] = true
    for (let i = 1; i <= n; i++) {
        // 3. 空字符串和 * 是匹配的
        if (dp[0][i - 1] && p[i - 1] == '*') {
            dp[0][i] = true
        }
    }

    // 状态转移
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s[i - 1] == p[j - 1] || p[j - 1] == '?') {
                dp[i][j] = dp[i - 1][j - 1]
            } else if (p[j - 1] == '*') {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j]
            }
        }
    }

    return dp[m][n]
};